package com.leetcode.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * @Author zhang.xin
 * @Description: TODO(这里描述)
 * @Date 2019/12/26
 */
public class Leetcode94 {



    /**
     * 解题思路：中序遍历会需要在遍历完左子树之后才遍历跟结点，因此需要先找到左子树的根结点，
     * 同时使用栈对之前的遍历的结点进行保存，以便找到当前结点的父节点。
     * 和本题类似的先序遍历的非递归算法，需要调整的只是结点的遍历顺序，先输出，在将其放入栈中。
     * @param root 根节点
     * @return 遍历序列
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        TreeNode temp = root;
        List<Integer> retList = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        while (temp != null || !stack.empty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            TreeNode node = stack.pop();
            retList.add(node.val);
            temp = node.right;
        }
        return retList;
    }

}
